home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / HPACK78S.ZIP / wildcard.c < prev    next >
C/C++ Source or Header  |  1992-12-03  |  9KB  |  332 lines
  1. /****************************************************************************
  2. *                                                                            *
  3. *                            HPACK Multi-System Archiver                        *
  4. *                            ===========================                        *
  5. *                                                                            *
  6. *                         Wildcard String Matching Routines                    *
  7. *                            WILDCARD.C  Updated 20/06/90                    *
  8. *                                                                            *
  9. * This program is protected by copyright and as such any use or copying of    *
  10. *  this code for your own purposes directly or indirectly is highly uncool    *
  11. *                      and if you do so there will be....trubble.                *
  12. *                 And remember: We know where your kids go to school.            *
  13. *                                                                            *
  14. *            Copyright 1989, 1990 Peter C.Gutmann.  All rights reserved        *
  15. *                                                                            *
  16. ****************************************************************************/
  17.  
  18. #include <ctype.h>
  19. #include <string.h>
  20. #include "defs.h"
  21. #include "error.h"
  22. #include "system.h"
  23. #include "wildcard.h"
  24.  
  25. /* The types we can match.  These are:
  26.  
  27.     END                    - End of string
  28.     MATCHEND            - Match all following chars
  29.     MATCHTO <end>        - Match all chars till <end>
  30.     MATCHONE            - Match any one char
  31.     RANGE <from> <to>    - Match all chars in range <from>...<to>
  32.     NOTRANGE <from> <to>- Match all chars but those in range <from>...<to>
  33.     <char>                - Match this char */
  34.  
  35. enum { END, MATCHEND, MATCHTO, MATCHONE, RANGE, NOTRANGE, ENDRANGE };
  36.  
  37. /* The escape character which is used to override standard wildcard
  38.    characters.  Usually this is '\' but MSDOS and OS/2 need to use '#' since
  39.    '\' is used in pathnames */
  40.  
  41. #if defined( __MSDOS__ ) || defined( __OS2__ )
  42.   #define ESC    '#'
  43. #else
  44.   #define ESC    '\\'
  45. #endif /* __MSDOS__ || __OS2__ */
  46.  
  47. /* A utility function to determine whether a string segment contains any
  48.    wildcard characters */
  49.  
  50. BOOLEAN hasWildcards( char *string, int count )
  51.     {
  52.     char ch;
  53.  
  54.     while( count-- )
  55.         if( ( ch = *string++ ) == '*' || ch == '?' || ch == '[' || ch == ESC )
  56.             return( TRUE );
  57.  
  58.     /* No wildcards found in string */
  59.     return( FALSE );
  60.     }
  61.  
  62. BOOLEAN strHasWildcards( char *string )
  63.     {
  64.     return( hasWildcards( string, strlen( string ) ) );
  65.     }
  66.  
  67. /****************************************************************************
  68. *                                                                            *
  69. *                         String "Compiling" Function                            *
  70. *                                                                            *
  71. ****************************************************************************/
  72.  
  73. /* Compile a string into a form acceptable by the wildcard-matching FSM.
  74.    The form is pretty simple.  The only part which may require a bit of
  75.    explanation is the mechanism for matching ranges.  This is given by the
  76.    RE { "^" | "!" }? { letter { "-" letter }? }+ */
  77.  
  78. int compileString( const char *src, char *dest )
  79.     {
  80.     int srcIndex = 0, destIndex = 0;
  81.     BOOLEAN inRange;
  82.     char ch;
  83.  
  84.     while( ( ch = src[ srcIndex++ ] ) && destIndex < MATCH_DEST_LEN )
  85.         switch( ch )
  86.             {
  87.             case '*':
  88. #ifdef AIX
  89.                 /* Fix a bug in the RS6000 cc optimizer where it gets a bit
  90.                    enthusiastic with reusing a CR which was set for the test
  91.                    of src[ srcIndex++ ] and doesn't notice that srcIndex has
  92.                    changed.  The following forces a reevaluation of
  93.                    src[ srcIndex ] */
  94.                 srcIndex--;
  95.                 srcIndex++;
  96. #endif /* AIX */
  97.                 if( src[ srcIndex ] )
  98.                     dest[ destIndex++ ] = MATCHTO;
  99.                 else
  100.                     dest[ destIndex++ ] = MATCHEND;
  101.  
  102.                 /* Stomp repeated '*'s */
  103.                 while( src[ srcIndex ] == '*' )
  104.                     srcIndex++;
  105.  
  106.                 break;
  107.  
  108.             case '?':
  109.                 dest[ destIndex++ ] = MATCHONE;
  110.                 break;
  111.  
  112.             case '[':
  113.                 if( src[ srcIndex ] == '^' || src[ srcIndex ] == '!' )
  114.                     {
  115.                     dest[ destIndex++ ] = NOTRANGE;
  116.                     srcIndex++;
  117.                     }
  118.                 else
  119.                     dest[ destIndex++ ] = RANGE;
  120.                 if( src[ srcIndex ] == ']' || src[ srcIndex ] == '-' )
  121. #ifdef GUI
  122.                     return( ERROR );
  123. #else
  124.                     error( BAD_WILDCARD_FORMAT, src );
  125. #endif /* GUI */
  126.  
  127.                 inRange = FALSE;
  128.                 while( ( ( ch = src[ srcIndex++ ] ) != ']' ) && \
  129.                                         ( destIndex < MATCH_DEST_LEN - 1 ) )
  130.                             /* destIndex < MATCH_DEST_LEN - 1 allows room for
  131.                                the ENDRANGE and END tokens */
  132.                     switch( ch )
  133.                         {
  134.                         case END:
  135. #ifdef GUI
  136.                             return( ERROR );
  137. #else
  138.                             error( BAD_WILDCARD_FORMAT, src );
  139.                             break;
  140. #endif /* GUI */
  141.  
  142.                         case '-':
  143.                             if( inRange )
  144. #ifdef GUI
  145.                                 return( ERROR );
  146. #else
  147.                                 error( BAD_WILDCARD_FORMAT, src );
  148. #endif /* GUI */
  149.                             inRange = TRUE;
  150.                             dest[ destIndex ] = dest[ destIndex - 1 ];
  151.                             dest[ destIndex - 1 ] = RANGE;
  152.                             destIndex++;
  153.                             break;
  154.  
  155.                         case ESC:
  156.                             if( !( ch = src[ srcIndex++ ] ) )
  157. #ifdef GUI
  158.                                 return( ERROR );
  159. #else
  160.                                 error( BAD_WILDCARD_FORMAT, src );
  161. #endif /* GUI */
  162.                             /* Drop through */
  163.  
  164.                         default:
  165.                             dest[ destIndex++ ] = ch;
  166.                             inRange = FALSE;
  167.                             break;
  168.                         }
  169.                 if( inRange )
  170. #ifdef GUI
  171.                     return( ERROR );
  172. #else
  173.                     error( BAD_WILDCARD_FORMAT, src );
  174. #endif /* GUI */
  175.                 dest[ destIndex++ ] = ENDRANGE;
  176.                 break;
  177.  
  178.             case ESC:
  179.                 if( !( ch = src[ srcIndex++ ] ) )
  180. #ifdef GUI
  181.                     return( ERROR );
  182. #else
  183.                     error( BAD_WILDCARD_FORMAT, src );
  184. #endif /* GUI */
  185.                 /* Drop through */
  186.  
  187.             default:
  188.                 dest[ destIndex++ ] = ch;
  189.             }
  190.     dest[ destIndex++ ] = END;
  191.  
  192.     /* Very complex regular expressions can overflow the destination buffer */
  193.     if( destIndex >= MATCH_DEST_LEN )
  194. #ifdef GUI
  195.         return( ERROR );
  196. #else
  197.         error( WILDCARD_TOO_COMPLEX );
  198. #endif /* GUI */
  199.  
  200.     /* Return count of no.of chars in output + null delimiter */
  201.     return( destIndex );
  202.     }
  203.  
  204. /****************************************************************************
  205. *                                                                            *
  206. *                        Wildcard String Matching Functions                    *
  207. *                                                                            *
  208. ****************************************************************************/
  209.  
  210. /* A simple queue, used to handle backtracking.  Once the queue is full, we
  211.    stop adding items, even if space has been freed up at the front.  This
  212.    conveniently stops deep recursion for very complex expressions.  The queue
  213.    size is chosen to be in the vicinity of the maximum filename length we can
  214.    expect, to allow for a worst-case scenario of matching "*x" to "xxxxx..." */
  215.  
  216. #define QUEUE_SIZE    50
  217.  
  218. static int srcQueue[ QUEUE_SIZE ], destQueue[ QUEUE_SIZE ], queueFront, queueEnd;
  219.  
  220. /* Match a pattern string with wildcards against a literal string */
  221.  
  222. BOOLEAN matchString( const char *src, const char *dest, const BOOLEAN hasWildcards )
  223.     {
  224.     char ch, matchChar;
  225.     int srcIndex = 0, destIndex = 0;
  226.     BOOLEAN match = TRUE, notFlag = FALSE, passedChar = FALSE;
  227.  
  228.     /* Simple case: If there are no wildcards, just do a straight compare */
  229.     if( !hasWildcards )
  230.         {
  231.         /* Check for special cases of empty string and differing string lengths */
  232.         if( strlen( src ) != strlen( dest ) )
  233.             return( FALSE );
  234.  
  235.         return( !caseStrcmp( src, dest ) );
  236.         }
  237.  
  238.     /* Set up queue for backtracking */
  239.     queueFront = queueEnd = 0;
  240.  
  241. retry:
  242.     while( ( ch = src[ srcIndex++ ] ) && match )
  243.         switch( ch )
  244.             {
  245.             case MATCHEND:
  246.                 return( match );        /* Match all remaining chars */
  247.  
  248.             case MATCHTO:
  249.                 matchChar = src[ srcIndex ];
  250.                 while( caseMatch( dest[ destIndex ] ) != matchChar && dest[ destIndex ] )
  251.                     {
  252.                     /* We can't do this as part of the main loop since that
  253.                        wouldn't let us do a match of 0 chars */
  254.                     destIndex++;
  255.                     passedChar = TRUE;    /* Remember we've matched at least one char */
  256.                     }
  257.  
  258.                 /* See if we exited due to running out of chars to match rather
  259.                    than an actual match */
  260.                 if( !dest[ destIndex ] )
  261.                     match = FALSE;
  262.                 else
  263.                     /* Push current state so we can backtrack */
  264.                     if( queueEnd < QUEUE_SIZE )
  265.                         {
  266.                         srcQueue[ queueEnd ] = srcIndex - 1;
  267.                         destQueue[ queueEnd++ ] = ( passedChar ) ? destIndex : destIndex + 1;
  268.                         }
  269.                 passedChar = FALSE;
  270.                 break;
  271.  
  272.             case MATCHONE:
  273.                 if( !dest[ destIndex++ ] )
  274.                     match = FALSE;
  275.                 break;
  276.  
  277.             case NOTRANGE:
  278.                 notFlag = TRUE;
  279.                 /* Drop through */
  280.  
  281.             case RANGE:
  282.                 /* Note that when checking for a match it is necessary to use
  283.                    "|=" to indicate a match, since we are not using short
  284.                    circuit evaluation and thus with "=" a later non-match may
  285.                    cancel a previous match.  Using short-circuit evaluation
  286.                    give little advantage, since it involves adding gotos to
  287.                    exit the loop, and yet we must still scan over src[]
  288.                    anyway to get to the ENDRANGE.  Note also that binary
  289.                    &'s are used in the comparisons to avoid short-circuit
  290.                    evaluation, since the expressions have side effects */
  291.                 match = FALSE;
  292.                 matchChar = caseMatch( dest[ destIndex ] );
  293.                 destIndex++;
  294.                 while( ( ch = src[ srcIndex++ ] ) != ENDRANGE )
  295.                     if( ch == RANGE )
  296.                         {
  297.                         /* Joining the following two statements with an '&'
  298.                            doesn't seem to work */
  299.                         match |= matchChar >= caseMatch( src[ srcIndex ] );
  300.                         srcIndex++;
  301.                         match &= matchChar <= caseMatch( src[ srcIndex ] );
  302.                         srcIndex++;
  303.                         }
  304.                     else
  305.                         match |= matchChar == caseMatch( ch );
  306.  
  307.                 if( notFlag )
  308.                     match = !match;
  309.                 notFlag = FALSE;
  310.                 break;
  311.  
  312.             default:
  313.                 match = caseMatch( ch ) == caseMatch( dest[ destIndex ] );
  314.                 destIndex++;
  315.             }
  316.  
  317.     /* No match if there are more matchable chars in one of the strings */
  318.     if( src[ srcIndex - 1 ] || dest[ destIndex ] )
  319.         match = FALSE;
  320.  
  321.     /* See if we can backtrack and try again */
  322.     if( !match && ( queueFront != queueEnd ) )
  323.         {
  324.         srcIndex = srcQueue[ queueFront ];
  325.         destIndex = destQueue[ queueFront++ ];
  326.         match = TRUE;
  327.         goto retry;
  328.         }
  329.  
  330.     return( match );
  331.     }
  332.